#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
using namespace std;

int find(vector<int>& nums)
{
	int left = 0, right = nums.size() - 1;
	while (left < right)
	{
		int m = left + ((right - left) >> 1);
		if (nums[m] == m) left = m + 1;
		else right = m;
	}
	return nums[right] == right ? right + 1: right;
}

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

class Solution {
public:
    vector<string> ret;
    void dfs(TreeNode* root, string s)
    {
        if (root->left == nullptr && root->right == nullptr)
        {
            s += to_string(root->val);
            ret.push_back(s);
            return;
        }
        else
            s += to_string(root->val), s += "->";
        if (root->left) dfs(root->left, s);
        if (root->right) dfs(root->right, s);
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        if (root == nullptr) return ret;
        string s = "";
        dfs(root, s);
        return ret;
    }

    bool satisfiesConditions(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        for (int i = 0; i <= n - 1; ++i)
        {
            for (int j = 0; j <= m - 1; ++j)
            {
                if (i + 1 <= n - 1 && grid[i + 1][j] != grid[i][j]) return false;
                if (j + 1 <= m - 1 && grid[i][j] == grid[i][j + 1]) return false;
            }
        }
        return true;
    }
};